CF559C Gerald and Giant Chess

如果没有不能走到的点，这道题就非常简单了。我们只需向下走$h-1$步，向右走$w-1$步，就可到达右下角。在这$h+w-2$步中，我们选$h-1$向下走，那么答案为$C_{h+w-2}^{h-1}$。

但是，棋盘中有些点是不能走的，我们考虑用容斥原理去除多余方案，即

$Ans=C_{h+w-2}^{h-1}-P_1+P_2+..+(-1)^n * P_n$

其中，$P_i$经过$i$个不能走的点的路径，但是，此题$n<=2000$，容斥原理直接炸掉。

但上面的思路给了我们启示，设$f_i$表示从$(1,1)$走到第$i$个不能走的点，且不经过其它不能走的点的方案数。那么有：

我们可以看出，转移时与下标先后顺序有关，我们先对下标排序，再进行计算。

我们将终点也看成一个不能走到的点，答案就为$f_{n+1}$

附上代码：

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
#define Mod 1000000007

const int MAXN = 2000 , MAXDEX = 100000;
int h , w , n , f[ MAXN + 5 ];
int Fac[ 2 * MAXDEX + 5 ] , Inv[ 2 * MAXDEX + 5 ];
struct node{
    int x , y;
    bool operator < ( const node &Other ) {
        if( x < Other.x )
            return 1;
        if( x == Other.x && y < Other.y )
            return 1;
        return 0;
    }
}a[ MAXN + 5 ];

int Quick_pow( int x , int po ) {
    int Ans = 1;
    while( po ) {
        if( po % 2 )
            Ans = 1ll * Ans * x % Mod;
        x = 1ll * x * x % Mod;
        po /= 2;
    }
    return Ans;
}
void Init( ) {
    int M = 2 * max( h , w );
    Fac[ 0 ] = 1;
    for( int i = 1 ; i <= M ; i ++ )
        Fac[ i ] = 1ll * Fac[ i - 1 ] * i % Mod;
    Inv[ M ] = Quick_pow( Fac[ M ] , Mod - 2 );		//费马小定理算出阶乘最后一项逆元
    for( int i = M - 1 ; i >= 0 ; i -- )
        Inv[ i ] = 1ll * Inv[ i + 1 ] * ( i + 1 ) % Mod;
    
    /*for( int i = 1 ; i <= M ; i ++ )
        printf("%d %d\n",Fac[ i ],Inv[ i ]);*/
}

int Combination( int n , int m ) {	//根据组合数定义
    if( n < m ) return 0;
    return 1ll * Fac[ n ] * Inv[ n - m ] % Mod * Inv[ m ] % Mod;
}

int main( ) {
    scanf("%d %d %d",& h , &w , &n );
    for( int i = 1 ; i <= n ; i ++ )
        scanf("%d %d",&a[ i ].x,&a[ i ].y);
    n ++;
    a[ n ].x = h , a[ n ].y = w;
    sort( a + 1 , a + n + 1 );
    Init( );
    
    for( int i = 1 ; i <= n ; i ++ ) {
        f[ i ] = Combination( a[ i ].x + a[ i ].y - 2 , a[ i ].x - 1 );
        for( int j = 1 ; j <= i - 1 ; j ++ )
            f[ i ] = ( ( 1ll * f[ i ] - 1ll * f[ j ] * Combination( a[ i ].x + a[ i ].y - a[ j ].x - a[ j ].y , a[ i ].x - a[ j ].x ) % Mod ) % Mod + Mod ) % Mod;
    }
    printf("%d\n",f[ n ]);
    return 0;
}